package LeetCode;

import java.util.HashMap;

public class LC_138_CopyListwithRandomPointer {
    public static void main(String[] args) {

    }

    class RandomListNode {
        int label;
        RandomListNode next, random;

        RandomListNode(int x) {
            this.label = x;
        }
    }

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) return null;
            HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
            RandomListNode newhead = new RandomListNode(head.label);
            map.put(head, newhead);
            RandomListNode oldp = head.next;
            RandomListNode newp = newhead;
            while (oldp != null) {
                RandomListNode newnode = new RandomListNode(oldp.label);
                map.put(oldp, newnode);
                newp.next = newnode;
                oldp = oldp.next;
                newp = newp.next;
            }
            oldp = head;
            newp = newhead;
            while (oldp != null) {
                newp.random = map.get(oldp.random);
                oldp = oldp.next;
                newp = newp.next;
            }
            return newhead;
        }
    }
}
